//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
// 
//
// 示例 2: 
//
// 
//输入: nums = [1], k = 1
//输出: [1] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// k 的取值范围是 [1, 数组中不相同的元素的个数] 
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 
// 
//
// 
//
// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 
//
// Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 👍 1521 👎 0


package leetcode.editor.cn;

import java.util.*;

/**
 * 前 K 个高频元素
 * @date 2023-04-10 10:12:11
 */
class P347_TopKFrequentElements{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P347_TopKFrequentElements().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
		/**
		 * HashMap<Integer,Integer> map = new HashMap<>();
		 * 		//使用HashMap来记录下各个数字出现的频率
		 * 		for (int num : nums) {
		 * 			if (map.containsKey(num)) {
		 * 				map.put(num, map.get(num) + 1);
		 *                        } else {
		 * 				map.put(num, 1);
		 *            }* 		}
		 * 		//遍历map，使用堆排序来保存频率最大的k个元素
		 * 		PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
		 *            @Override
		 *            public int compare(Integer o1, Integer o2) {
		 * 				return map.get(o1) - map.get(o2);
		 *            }
		 *        });
		 * 		for (Integer key : map.keySet()){
		 * 			if(pq.size() < k){
		 * 				pq.add(key);
		 *            }else if(map.get(key) > map.get(pq.peek())){
		 * 				pq.remove();
		 * 				pq.add(key);
		 *            }
		 *        }
		 * 		List<Integer> res = new ArrayList<>();
		 * 		while(!pq.isEmpty()){
		 * 			res.add(pq.remove());
		 *        }
		 * 		int[] ans = res.stream().mapToInt(Integer::intValue).toArray();
		 * 		return ans;
		 */
		//方法二、桶排序
//		设置若干个桶，每个桶存储出现频率相同的数。桶的下标表示数出现的频率，即第 i 个桶中存储的数出现的频率为i。
//		把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
		HashMap<Integer,Integer> map = new HashMap<>();
		for (int num : nums){
			if(map.containsKey(num)){
				map.put(num,map.get(num)+1);
			}else{
				map.put(num,1);
			}
		}
		List<Integer>[] buckets = new ArrayList[nums.length+1];
		for (int key : map.keySet()){//按照频率分桶
			int fre = map.get(key);
			if(buckets[fre] == null){
				buckets[fre] = new ArrayList<>();
			}
			buckets[fre].add(key);
		}
		List<Integer> res = new ArrayList<>();
		for (int i = buckets.length - 1; i >= 0 && res.size() < k; i--) {
			if(buckets[i] == null){
				continue;
			}
			if(buckets[i].size() < k - res.size()){//链表的长度小于可用空间
				res.addAll(buckets[i]);
			}else{
				res.addAll(buckets[i].subList(0,k- res.size()));
			}
		}
		int arr[] = res.stream().mapToInt(Integer::intValue).toArray();
		/**
		 *int ans[] = new int[res.size()];
		 * for(int i = 0;i < res.size();i++){
		 * 	 ans[i] = res.get(i);
		 *  }
		 */

		return arr;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
